package binaryresearchtree;

import sun.reflect.generics.tree.Tree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-07-19
 * Time: 18:35
 */
public class BinarySearchTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }

    public TreeNode root;
    public boolean search(int key){
        TreeNode cur = root;
        while(cur != null){
            if (cur.val > key){
                cur = cur.left;
            }else if(cur.val < key){
                cur = cur.right;
            }else{
                return true;
            }
        }
        return false;
    }


    public boolean insert(int val){

        //第一步：先把根节点插入进去
        if (root == null){
            root = new TreeNode(val);
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;

        //第二步：有了根节点，再去确定要插入的位置，关键是cur为null时就停止循环，parent去记录值
        while(cur != null){
            if (cur.val > val){
                parent = cur;
                cur = cur.left;
            }else if(cur.val < val ) {
                parent = cur;
                cur = cur.right;
            }else{
                return false;
            }
        }
        //第三步：插入，实例化一个带val参数的节点，去跟parent.val比较，然后插入

        //第一种一种写法，很简洁，不要去纠结，cur的值，cur的作用就是做循环的一个条件
        TreeNode root = new TreeNode(val);
        if(parent.val > val){
            parent.left = root;
        }else {
            parent.right = root;
        }

        /*
        当cur 直到最下面时（最后），cur指向null
        cur的位置是正确的，但是我们在实例化一个节点，去比较插入让思路更加清楚
        cur = new TreeNode(val);
        //parent在最后一次循环中不用走到底，但是在中间循环时候，它得继续往下面走
        if(parent.val > cur.val){
            parent.left = cur;
        }else {
            parent.right = cur;
        }
        */

        //插入完了最后返回true就可以了
        return true;
        //测试的时候，给个数组遍历插入就可以了，每次插入的话都在叶子节点，
    }
    public void remove(int key){
        //第一步先锁定二叉搜索树中是否含有我们需要查找到的关键字key，用parent记录下来
        //这里就体现出来了，为什么上面inser方法中要单独用cur记录一下root，让cur去走代码
        TreeNode cur = root;
        TreeNode parent = null;

        while(cur != null){
            if (cur.val > key){
                parent = cur;
                cur = cur.left;
            }else if(cur.val < key ) {
                parent = cur;
                cur = cur.right;
            } else{      //最后cur.val = key 进入remove函数
                removeNode(parent,cur);
            }
        }
    }

    public void removeNode(TreeNode parent , TreeNode cur){
        //思考why大情况要这么分，小情况要这么分就能覆盖所有的情况
       /* 三种大情况
       *  一：cur.left = null  二：cur.rigth = null  三：cur的两边都不为null
       * 每一种大情况在分小情况    1：cur在root位置  2：cur在parent.left   3:cur在parent.right
       * */
        if (cur.left == null){
            if (cur == root){
                cur = cur.right;     //这里因为要更改的是根节点root，所以直接用root覆盖,
            }else if (cur == parent.right){
                parent.right = cur.right;
            }else {   //这里直接进else就可以了,因为只有三种情况
                parent.left = cur.right;
            }
        }else if (cur.right == null){
            if (cur == root){
                root = cur.left;

            }else if (cur == parent.right){
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }

        }else{
            /*思路看图去想，是一种替代+删除的想法*/
            /*这里是用了其中一种思路，去找cur右树中最小的val节点，即右树中最左边的节点*/


           /* TreeNode targetParent = cur.right;
            TreeNode target = targetParent.left;*/

            //这么去写
            TreeNode targetParent = cur;
            TreeNode target = cur.right;


            while(target.left != null){
                targetParent = target;
                target = target.left;
            }
            /*跳出循环就是找到了最小值的节点*/
            //更换cur的值
            cur.val = target.val;

            /*删除target
            * 又分两种情况
            * tatget在tp的左边*/
            if(target == targetParent.left ){
                targetParent.left = target.right;
            }else{
                targetParent.right = target.right;
            }

        }

    }







}
